Міністерство освіти і науки, молоді та спорту України
Національний університет ″Львівська політехніка″
Кафедра БІТ
Звіт
про виконання лабораторної роботи №4
з курсу “ АЛГОРИТМІЧНІ ОСНОВИ КРИПТОЛОГІЇ ”
на тему: “ АЛГОРИТМИ ФАКТОРИЗАЦІЇ СКЛАДЕНИХ ЧИСЕЛ”
Варіант № 1
Львів 2013
Мета роботи: вивчитити основні алгоритми факторизації складених чисел
1. ОСНОВНІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Для криптографічного зламування алгоритму шифрування RSA достатньо розкласти частину відкритого ключа на прості множники, тому завдання факторизації складеного числа є актуальним. Дане завдання зворотне до завдання визначення простоти конкретного числа, але набагато складніше. Далі наведено найбільш прості методи факторизації складеного числа.
1.3. Метод ρ - Полларда.
Алгоритм:
1. Вибираємо випадковим чином xi з множини {0,1,…,n-1}; yx1; k2.
2. ii+1 і обчислюємо наступний елемент послідовності
xif(xi-1)mod n.
3. Якщо dHСД(y- xi, n): d1 і dn то d дільник n, цикл завершений.
4. Якщо i дорівнює k, то y xi, k2k.
Можливо, що кількість значень за модулем n виявиться більшим ніж . Метод має евристичну оцінку складності O(n1/4) арифметичних операцій. Він використовується для відділення невеликих простих дільників факторизованого числа n.
Основна ідея даного методу така. Якщо період послідовності xi mod n може бути порядку n, то період послідовності xi mod p для простого дільника p числа n не перевищує p. Це означає, що y і xi можуть бути різними за модулем n, але збігатися за модулем p.
Існує константа c, така, що для будь-якого >0 ймовірність не знайти нетривіальний дільник n за clog3n бітових операцій буде меншою, ніж e.
2. ЗАВДАННЯ
1. Реалізувати програму, що дозволяє знаходити розклад на множники заданого числа n:
a) методом пробних ділень;
б) згідно заданого варіанту в таблиці 1;
в) комбінованим методом: на першому етапі методом пробних ділень перевіряється розкладність n; якщо n пройшло цей тест, то на другому етапі застосовуйте заданий у варіанті алгоритм.
Слід зважати на те, що всі представлені методи шукають тільки один дільник n. Таким чином, необхідно застосовувати метод кілька разів, поки не вийде повний розклад числа на множники.
2. Приступаючи до факторизації числа, потрібно спочатку переконатися, що воно не просте за допомогою тестів на простоту. Ці тести простоти, як правило, потребують значно менше часу, ніж алгоритми факторизації. Парне число також не потрібно факторизувати.
3. Порівняти два реалізовані методи за часом розкладу досить великого n (наприклад, з 15-ма десятковими розрядами).
4. У методі пробних ділень обмежитися діленням на такі прості числа:
2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,19,193,197,199,211,223,227,229,233,239,241,251.
5. У звіті обов'язково повинні бути присутніми тести, підтверджуючі правильність розроблених програм.
Варіант
Алгоритм факторизації
Доповнення
1
Метод ρ-Поларда
3. Блок-схема алгоритму
randomNumber(int n)
factorise(int n)
check(int secondDiv)
SCD(int firstNumber, int secondNumber)
button1_Click(object sender, EventArgs e)
4. Cписок ідентифікаторів констант, змінних, функцій, використаних у блок-схемі алгоритму і програмі, та їх пояснення.
massDiv – масив типу int, що приймає значення дільників;
j, x, oldx, d – змінні типу int, що використовуються у методі р-Полларда;
n — змінна, що факторизується;
correction — змінна, що відповідає за точність результату;
randomNumber()– метод, що генерує випадкове число;
check()– метод логічного типу, що повертає відповідне значеня в залежності від числа;
factorise ()– метод р-Полларда факторизації складного числа;
SCD ()– метод, що повертає найменше спільне кратне двох чисел;
Form1_Load ()– метод, що виконується безпосередньо післа завантаження програми;
button1_Click () – метод, який виконує моделацію натиску на програмну кнопку;
5. Текст програми
using System;
using System.Collections.Generic;...
